#include <vector>
using namespace std;
#include <iostream>


//version 1
class Solution0 {
public:
    int MergeSortAndFind(vector<int>& tmp, vector<int>& nums, int left, int right) {
        if (left >= right) return 0;

        int mid = left + (right - left) / 2;
        //[left, mid] [mid + 1, right]
        int l = MergeSortAndFind(tmp, nums, left, mid);
        int r = MergeSortAndFind(tmp, nums, mid + 1, right);
        int cur1 = left, cur2 = mid + 1, ret = l + r, i = left;

        //先来进行判断当前的翻转对个数
        //走到这里，左右两边都是一个降序数组
        //因为这一次比较不是单纯一比一 比大小，所以不能在归并的同时来进行查找翻转对
        while(cur1 <= mid && cur2 <= right){
            long long num1 = nums[cur1], num2 = nums[cur2];
            if(num1 <= 2 * num2) ++cur2;
            else{
                ret += (right - cur2 + 1);
                ++cur1;
            }
        }

        //复位cur1和cur2，为了后序进行归并排序
        cur1 = left;
        cur2 = mid + 1; 

        //归并排序
        while (cur1 <= mid && cur2 <= right) {
            if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur2++];
            else tmp[i++] = nums[cur1++];
        }

        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        //处理辅助数组
        for (int j = left; j < i; ++j) nums[j] = tmp[j];

        //返回结果
        return ret;
    }



    

    int reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        return MergeSortAndFind(tmp, nums, 0, nums.size() - 1);
    }
};



//version2

class Solution1 {
public:
    int MergeSortAndFind(vector<int>& tmp, vector<int>& nums, int left, int right) {
        if (left >= right) return 0;

        int mid = left + (right - left) / 2;
        //[left, mid] [mid + 1, right]
        int l = MergeSortAndFind(tmp, nums, left, mid);
        int r = MergeSortAndFind(tmp, nums, mid + 1, right);
        int cur1 = left, cur2 = mid + 1, ret = l + r, i = left;

        //先来进行判断当前的翻转对个数
        //走到这里，左右两边都是一个升序数组
        //因为这一次比较不是单纯一比一 比大小，所以不能在归并的同时来进行查找翻转对
        //升序的时候，是在前面找所有的数字，该数字的一半比当前数字还要大！
        while(cur1 <= mid && cur2 <= right){
            long long num1 = nums[cur1], num2 = nums[cur2];
            if(num1 * 0.5 <= num2) ++cur1;
            else{
                ret += (mid - cur1 + 1);
                ++cur2;
            }
        }

        //复位cur1和cur2，为了后序进行归并排序
        cur1 = left;
        cur2 = mid + 1; 

        //归并排序
        while (cur1 <= mid && cur2 <= right) {
            if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];
            else tmp[i++] = nums[cur2++];
        }

        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        //处理辅助数组
        for (int j = left; j < i; ++j) nums[j] = tmp[j];

        //返回结果
        return ret;
    }

    int reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        return MergeSortAndFind(tmp, nums, 0, nums.size() - 1);
    }
};